package q540_singleNonDuplicate;

public class Solution {
    /*
    此题仍然要是用二分查找的模版
    需要考虑的是 当单个数出现的时候 对数组产生了什么样的影响
    没有出现单个数的时候 偶数位的数和它下一个位的数是一样的
    而出现之后 就变为奇数位的数和它下一个位的数是一样的
    因此 我们根据当前mid的情况不断的调整窗口左右两侧 最后就能够得到
     */
    public int singleNonDuplicate(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + ((r - l) >> 1);
            if (mid % 2 == 0 && (mid + 1 < nums.length) && nums[mid] == nums[mid + 1] || (mid % 2 != 0 && (mid - 1 >= 0) && nums[mid] == nums[mid - 1])) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return nums[l];
    }
}
